package com.dy.分类.递归回溯分治.计算右侧小于当前元素的个数;
/*
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质：
counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 思路：归并排序，分治,需要建立map存储num和索引i的关系，便于更新count
 */

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> count = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            count.add(0);
        }
        int[][] tmp = new int[nums.length][2];
        int[][] num = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            num[i][0] = nums[i];
            num[i][1] = i;
        }
        mergeSort(num, tmp, 0, nums.length - 1, count);

        return count;

    }

    void mergeSort(int[][] nums, int[][] tmp, int start, int end,
                   List<Integer> count) {
        if (start < end) {
            int mid = start + (end - start) / 2;
            mergeSort(nums, tmp, start, mid, count);
            mergeSort(nums, tmp, mid + 1, end, count);
            merge(nums, tmp, start, mid, end, count);
        }
    }

    /**
     * 2 4 6 8       1 3 5 7
     */
    void merge(int[][] nums, int[][] tmp, int start, int mid, int end, List<Integer> count) {
        int i = mid;//从后往前merge
        int j = end;
        int k = end;
        while (i >= start && j > mid) {
            if (nums[i][0] > nums[j][0]) {
                int countTmp = count.get(nums[i][1]);
                count.set(nums[i][1], countTmp + j - mid);
                tmp[k][0] =nums[i][0];
                tmp[k][1] =nums[i][1];
                i--;k--;

            } else {
                tmp[k][0] =nums[j][0];
                tmp[k][1] =nums[j][1];
                k--;j--;
            }
        }
        while (i >= start) {
            tmp[k][0] =nums[i][0];
            tmp[k][1] =nums[i][1];
            i--;k--;
        }
        while (j > mid) {
            tmp[k][0] =nums[j][0];
            tmp[k][1] =nums[j][1];
            k--;j--;
        }
        for (int m = start; m <= end; m++) {
            nums[m][0] =tmp[m][0];
            nums[m][1] =tmp[m][1];
        }
//        Arrays.stream(nums).forEach(System.out::print);
//        System.out.println();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> s = solution.countSmaller(new int[]{26, 78, 27, 100, 33, 67, 90, 23, 66, 5, 38, 7, 35, 23, 52, 22, 83, 51, 98, 69, 81, 32, 78, 28, 94, 13, 2, 97, 3, 76, 99, 51, 9, 21, 84, 66, 65, 36, 100, 41});

        System.out.println(s);
    }
}
